package leetcode.linkedlist;

/**
 * 19. 删除链表的倒数第 N 个结点
 *
 */
public class RemoveNthFromEnd {

    public static void main(String[] args) {
        RemoveNthFromEnd solution = new RemoveNthFromEnd();
        Integer[] arr1 = {1, 2, 3, 4, 5};
        ListNode head = ListNode.makeLinkedList(arr1);

        ListNode resList = solution.removeNthFromEnd(head, 2);
        System.out.println(resList);
    }

    /**
     * 双指针法
     * 只需要遍历一遍(最优解)
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 添加哑节点
        ListNode dummy = new ListNode(0, head);
        ListNode right = head;
        ListNode left = dummy;
        for (int i = 0; i < n; ++i) {
            right = right.next;
        }
        while (right != null) {
            right = right.next;
            left = left.next;
        }
        left.next = left.next.next;
        return dummy.next;
    }

}
